package DP.背包.万诺复习;

import org.junit.Test;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
背包3总
背包MHmoban

本题：
    因为本身就是纯汉译解
    所以 题感写即可
 */
public class 无限零钱_版本3_DP {
    @Test
    public void test() {
        int[] c = {1,2,5};
        int a = 11;
        System.out.println(coinChange(c,a));
    }

    public int coinChange(int[] coins, int amount) {
        int[] c = coins;
        int am = amount;

        // 前n个 cur钱 = 最少币个
        int[][] dp = new int[c.length+1][am+1];

        // 这里只是初始化为0
        // * -> for里面还要if跳过该值->直接用本值
        for (int j = 1; j <= am; j++) {
            dp[0][j] =  999;
        }
        // cS不用初始化 因为右侧=0是0，<0有if卡

        for (int pN = 1; pN <= c.length; pN++) {
            for (int cS = 1; cS <= am; cS++) {
                int cI = pN-1;
                int na = 999; // 求min，没拿应该是999，被Math筛掉
                if(cS-c[cI]>=0) {
                    na = dp[pN][cS - c[cI]] + 1; // 选择不少 无限个
                }
                int buna = dp[pN - 1][cS]; // 不拿就是不拿 选择少掉
                dp[pN][cS] = Math.min(na,buna);
            }
        }
        return dp[c.length][am]==999?-1:dp[c.length][am];
    }
}
